﻿
//方法一：暴力匹配
//思路及算法
//
//我们可以让字符串 needle\textit{ needle }needle 与字符串 haystack\textit{ haystack }haystack 的所有长度为 mmm 的子串均匹配一次。
//
//为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，
//对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回 −1 - 1−1。



//int strStr(char* haystack, char* needle) {
//    int n = strlen(haystack), m = strlen(needle);
//    for (int i = 0; i + m <= n; i++) {
//        bool flag = true;
//        for (int j = 0; j < m; j++) {
//            if (haystack[i + j] != needle[j]) {
//                flag = false;
//                break;
//            }
//        }
//        if (flag) {
//            return i;
//        }
//    }
//    return -1;
//}



//方法二：Knuth - Morris - Pratt\text{ Knuth - Morris - Pratt }Knuth - Morris - Pratt 算法

//int strStr(char* haystack, char* needle) {
//    int n = strlen(haystack), m = strlen(needle);
//    if (m == 0) {
//        return 0;
//    }
//    int pi[m];
//    pi[0] = 0;
//    for (int i = 1, j = 0; i < m; i++) {
//        while (j > 0 && needle[i] != needle[j]) {
//            j = pi[j - 1];
//        }
//        if (needle[i] == needle[j]) {
//            j++;
//        }
//        pi[i] = j;
//    }
//    for (int i = 0, j = 0; i < n; i++) {
//        while (j > 0 && haystack[i] != needle[j]) {
//            j = pi[j - 1];
//        }
//        if (haystack[i] == needle[j]) {
//            j++;
//        }
//        if (j == m) {
//            return i - m + 1;
//        }
//    }
//    return -1;
//}
